#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
ll x;
int k;
ll rec[100005];
ll pre[20];
ll chuli[20][100005];

int main()
{
    for(int j=1;j<=9;j++){
        for(int num=0;num<=9;num++){
            pre[num]=1;
            for(int l=1;l<=j;l++){
                pre[num]*=num;
            }
        }
        for(int i=0;i<=99999;i++){
            ll ans=0;
            int tmp=i;
            while(tmp){
                int t=tmp%10;
                ans+=pre[t];
                tmp/=10;
            }
            chuli[j][i]=ans;
        }
    }
    int t;
    scanf("%d", &t);
    for(int tt=1;tt<=t;tt++){
        ll ans=0;
        printf("Case #%d: ", tt);
        scanf("%lld%d", &x, &k);
        for(ll i=0;i<=99999;i++){
            rec[i]=chuli[k][i]-i;
        }
        sort(rec, rec+100000);
        for(ll i=0;i<=99999;i++){
            ll tmp=chuli[k][i]-i*100000;
            ans+=upper_bound(rec, rec+100000, x-tmp)-lower_bound(rec, rec+100000, x-tmp);
        }
        printf("%lld\n", ans);
    }
}

